Public-key cryptography, or asymmetric-key cryptography, underlies many network transactions that occur today. Unlike symmetric-key cryptography, which relies upon a single key to both encrypt and decrypt data, public-key cryptography uses a pair of keys—a public key and a private key. A public key and private key are related in that information encrypted with a public key can be decrypted by the corresponding private key, and vice-versa. The public key is published while the private key is kept secret. If a sender of data authenticates that a published public key originated from a desired recipient (generally established through a trusted source, such as a certificate authority on the Internet), the sender can then encrypt the data to be sent using the public key, and, in theory, only the desired recipient (as the sole party in possession of the private key) can decrypt it.
Another use of public-key cryptography is digital signatures, which is a method to verify that a message was actually sent by the party expected to send it. When a sending party wishes to digitally sign a message for verification purposes, it uses its private key to encrypt a hash table (also known as a message digest) representation of the message itself. Then, the recipient can use the public key of the sender, authenticated by a trusted source, to decrypt the digital signature. If the recipient successfully decrypts the hash table, unique to the message being sent, with the authenticated private key, this verifies that the message was sent by the expected sender. This is true because, in theory, the message could only have originated from the expected sender, since it is the only party in possession of the private key corresponding to the public key used to decrypt the signature.
Encryption strength is related to the difficulty of discovering the key, which in turn depends on both the cryptographic algorithm (generally called a “cipher”), and the length of the key. (The ciphers themselves are published for evaluation by the cryptographic community, leaving only the key unknown.) For example, the difficulty of discovering the key for the RSA cipher (most commonly used for public-key encryption) depends on the difficulty of factoring large numbers, a well-known mathematical problem. In general, longer keys provide stronger encryption. Thus, a 128-bit key used with a particular cipher will provide much better cryptographic protection than a 40-bit key used with the same cipher.
Similarly, different ciphers may require different key lengths to achieve the same level of encryption strength. For example, the RSA cipher used for public-key encryption can only use a subset of all possible values for a key of a given length, due to the nature of the mathematical problem on which it is based. Other ciphers, such as those used for symmetric key encryption, can use all possible values for a key of a given length, rather than a subset of those values. Thus, a 128-bit key for use with a symmetric-key encryption cipher would provide stronger encryption than a 128-bit key for use with the RSA public-key encryption cipher. In practice, the RSA public-key encryption cipher (the most common form of public-key encryption) must use at least a 512-bit key to be considered cryptographically “strong,” whereas symmetric key ciphers can achieve approximately the same level of strength with a 64-bit key.
There are different methods to break encryption. The most basic method is the “brute force” method, in which a hacker might try every possible key, which, in theory, is guaranteed to result in success eventually. Other methods are cipher-specific. For example, generating public-private key pairs using the RSA cipher requires a “modulus” (i.e., key) that is comprised of two prime numbers, “p” and “q.” To determine a RSA private key from a RSA public key (and hence break the encryption), the modulus must be factored into “p” and “q.” This is a particularly difficult task as the size of the modulus increases. Thus, if a modulus is 512 bits, it must be factored into two 256-bit prime numbers (“p” and “q”) to break the encryption. In 1997, a specific assessment of the security of the 512-bit RSA keys showed that one may be factored for less than one million dollars and eight months of effort, and in 1999, the 512-bit number RSA-155 was factored in seven months. This means that 512-bit keys no longer provide sufficient security for anything more than very short-term security needs. RSA laboratories currently recommends key sizes of 1024 bits for corporate use, and 2048 bits for extremely valuable keys. The problems with using such long-length keys will be discussed further below.
The rate at which encryption schemes are broken continues to increase. This is true, in part, because processor capacity continues to double approximately every 18 months, in accordance with Moore's law. Weaker encryption can now be decrypted by using distributed processing over a relatively small number of computers. Because public-key encryption is, on average, weaker than symmetric-key encryption, it is particularly susceptible to cracking. However, it is also not feasible to simply increase the length of public keys, as it takes a substantial amount of time to encrypt and decrypt data using a very long key. For example, doubling the modulus of a RSA key will increase the time required for public key operations (such as encryption and signature verification) by a factor of four, on average, and will increase the time taken by private key operations (such as decryption and digital signing) by a factor of eight, on average. Further, key generation time will increase by a factor of 16 if the modulus is doubled.
The increased processing time for cryptographic operations using long keys is problematic in systems requiring fast communications, and for large-scale, multiple-computer request processing (e.g., an Internet server). Similarly, portable electronic devices generally cannot support the level of processing required for longer-length keys to ensure secure communications. For example, devices such as cell phones, PDAs, and facsimile machines have very limited processing capabilities, and would not be able to readily perform public or private key operations with the length of keys required for secure communications. Thus, because public-key cryptography is a time-consuming and processor-intensive means to securely exchange data, it is oftentimes used only initially to setup a secure exchange to be conducted using symmetric keys. There are two principal ways in which this occurs.
In one public-key/symmetric key encryption scheme, for each message to be transmitted, a temporary random “session” key of fixed length, typically shorter than the message itself, is generated. The session key is encrypted by using a public-key algorithm and the intended recipient's public key, and appended to the front of the message to be sent. The original message is then encrypted using a faster symmetric-key algorithm, utilizing the session key. The entire message thus includes the public-key-encrypted session key, followed by the session-key-encrypted original message. Upon receipt, the recipient (whose public key was used to encrypt the session key) uses its corresponding private key to decrypt the session key. The recipient then uses the decrypted session key to decrypt, at a faster rate than could be done with the public/private keys, the original message. In this scenario, the generation of a random session key occurs for each transmitted message.
In another public-key/symmetric key encryption scheme, a session key is generated for an entire communications session. In this scheme, only the session key, after being encrypted by the intended receiver's public key, is sent to the recipient. The recipient decrypts the session key using its private key. Then, the session key, now in possession of both the sender and recipient, is used in conjunction with a symmetric-key algorithm to rapidly encrypt and decrypt data that is communicated between the parties, at a much faster rate than could be accomplished using the public or private keys. The same session key can be used throughout the communications session (e.g., receiving a streaming video over the Internet) without having to conduct another public-key cryptography operation.
A common type of session key is a 64-bit Data Encryption Standard (DES) key for use with the DES cipher. The DES cipher is a block cipher, meaning that it takes a 64-bit data message as input (also referred to as “plaintext”), and outputs a 64-bit encrypted data message (also referred to as “ciphertext”). Block ciphers like DES are much faster than the calculations required for public-key algorithms like RSA.
The principal problem with symmetric keys (or “secret” keys) is finding a method to securely exchange them. As described above, with the advent of public-key cryptography, this problem has been substantially resolved. Therefore, the optimum combination of security and speed provided by dual public-key/symmetric-key encryption schemes (e.g., RGA/DES) underlie many encryption schemes currently in use on the Internet, like the SSL (Secure Sockets Layer) Handshake protocol.
A representation of a public-key encryption exchange of a symmetric key is shown in FIG. 1. As shown, the Sender wishes to provide a session key, “k,” to the Intended Receiver. The Receiver has a public/private key pair, “e, d,” compatible with a cipher such as RSA. The Receiver provides its public key “e” to the Sender, which as shown occurs directly, but can also occur indirectly through a trusted source like a certificate authority, which can verify its authenticity. Using this public key, the Sender encrypts the session key to generate encrypted session key “1” (i.e., “Ee(k)=1”). It then transmits the encrypted key to the Receiver, which decrypts it using its corresponding private key “d” to generate the original key “k” (i.e., “Dd(1)=k”).
A public-key encrypted exchange of a symmetric key can also occur for multiple intended receivers for group communications, as shown in FIG. 2. In this context, each intended receiver will have its own public/private key pair (i.e. “e1, d1” for Intended Receiver 1; “e2, d2” for Intended Receiver 2; “e3, d3” for Intended Receiver 3). The Sender will separately encrypt the session key using each Intended Receiver's public key, which is then uniquely decryptable by only the appropriate Intended Receiver. Each version of the encrypted key (i.e., “11,” “12,” “13”) will be entirely distinct from the other versions, but the end-result decrypted session key “k” will be the same for each Receiver.
One problem of the public-key/symmetric-key encryption scheme is what is commonly referred to as the “man-in-the-middle” problem. In this situation, an adversary interjects itself between the sender and the intended receiver, masquerading as the intended receiver to the sender, and as the sender to the intended receiver. This scenario is shown in FIG. 3. In this case, as with FIG. 1, a Sender is attempting to send a key “k” to the Intended Receiver.
However, this time an Adversary intercepts the Intended Receiver's public key “e,” and then provides its own public key “f” to the Sender instead. The Sender unknowingly uses the Adversary's public key to encrypt “k,” generating encrypted key “t,” which the Sender attempts to send to the Intended Receiver, but which is again intercepted by the Adversary. The Adversary uses its corresponding private key “g” to decrypt the symmetric key “k” sent by the Sender. The Adversary can now communicate freely with the Sender using the symmetric key, “k.”
Next, the Adversary encrypts the now-decrypted symmetric key “k” (or, alternatively, the Adversary's own symmetric key) with the intercepted public key “e” of the Intended Receiver, which it then sends to the Intended Receiver. The Intended Receiver, not realizing it is being duped and thinking that it has just received the Sender's encrypted symmetric key, decrypts the key using its corresponding private key “d.” The Intended Receiver can now freely communicate securely with the Adversary, which it thinks is the Sender. As the “man-in-the-middle,” the Adversary can intercept messages from the Sender to the Intended Receiver, or vice-versa, decrypt them, and then send them on or modify them as desired. It is difficult with this arrangement to detect the Adversary.
One way to avoid this issue, however, is to use a trusted source like a certificate authority to obtain public keys, which authenticates that a public key originates from a desired intended recipient. However, this is not always practical or possible. Having trusted sources requires a substantial infrastructure, which is not always feasible outside of the context of large networks like the Internet. Also, while the certificate authorities provide public-key verification for many major Internet sites, it would be impractical to keep an authenticated list of public keys for every individual user or computer on a wide-area network, for example. Furthermore, even if a trusted source of public keys is available, monitoring and accessing the trusted source to obtain dynamically changing content would consume substantial resources. This is particularly true if trusted sources must be accessed every time a communication is initiated. Also, obtaining and maintaining a table of public keys would be a very difficult undertaking for personal electronic devices like cell phones or facsimile machines.
For these reasons, it is desirable to have a method and system for secure key exchange that does not utilize public-key cryptography, while being simple enough to be used by devices like cell phones and facsimile machines having minimal processing capacity.